package com.fanco.learn_datastruct_leetcode.leetcode;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * input:  s = "aadbs" t= "bs"
 * output: bs
 *
 * @author Fanco
 */
public class Day33 {
    public static void main(String[] args) {

        Solution solution = new Solution();
    }

    private static class Solution {
        /**
         * 整体思路： 滑动窗口指针 实现。 左指针用来收缩，右指针用来延伸，保证包围的范围内
         * 存在所有 t 的所有字母，然后不断缩小窗口。
         * <p>
         * 问题在于如何判断 窗口可以完美包含 t的所有字符。
         *
         * @param s
         * @param t
         * @return
         */

        Map<Character, Integer> origin = new HashMap<>();
        Map<Character, Integer> current = new HashMap<>();

        public String minWindow(String s, String t) {
            int length = t.length();
            for (int i = 0; i < length; i++) {
                char c = t.charAt(i);
                origin.put(c, origin.getOrDefault(c, 0) + 1);
            }

            int left = 0;
            int right = -1;

            int len = Integer.MAX_VALUE;
            int ansL = -1, ansR = -1;

            int sLen = s.length();
            while ( right < sLen) {
                ++right;
                if (right < sLen && origin.containsKey(s.charAt(right))) {
                    current.put(s.charAt(right), current.getOrDefault(s.charAt(right), 0) + 1);
                }
                while (check() && left <= right) {
                    if (right - left + 1 < len) {
                        len = right - left + 1;
                        ansL = left;
                        ansR = left + len;
                    }
                    if (origin.containsKey(s.charAt(left))) {
                        current.put(s.charAt(left), current.getOrDefault(s.charAt(left), 0) - 1);
                    }
                    ++left;
                }
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }

        private boolean check() {
            Iterator iter = origin.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry) iter.next();
                Character key = (Character) entry.getKey();
                Integer val = (Integer) entry.getValue();
                if (current.getOrDefault(key, 0) < val) {
                    return false;
                }
            }
            return true;
        }
    }
}
